﻿#include <iostream>
#include <algorithm>
#include <unordered_set>

using namespace std;

typedef struct
{
	int start;
	int end;
}Project;

static bool projectCompare(const Project& a, const Project& b)
{
	return a.end < b.end;
}

#define MAX(a, b) (a > b ? a : b)

static int recur(const Project* projects, size_t projectSize, int index, unordered_set<int>& exists)
{
	if (index >= projectSize) return 0;
	
	Project cur = projects[index];
	int useCur = 0;
	bool conflictExists = false;
	for (auto it = exists.begin(); it != exists.end(); it++)
	{
		Project proj = projects[*it];
		if (
			(cur.start < proj.start && proj.start < cur.end) ||
			(cur.start < proj.end && proj.end < cur.end) ||
			(proj.start < cur.start && cur.end < proj.end) ||
			(cur.start < proj.start && proj.end < cur.end)
			)
		{
			conflictExists = true;
			break;
		}
	}

	if (!conflictExists)
	{
		exists.insert(index);
		useCur = 1 + recur(projects, projectSize, index + 1, exists);
		exists.erase(index);
	}

	int notUseCur = recur(projects, projectSize, index + 1, exists);
	return MAX(useCur, notUseCur);
}

//  一些项目要占用一个会议室宣讲，会议室不能同时容纳两个项目的宣讲。给你每一个项目开始的时间和结束
// (给你一个数组，里面是一个个具体的项目), 你来安排宣讲的日程，要求会议室进行的宣讲场次最多。
// 返回这个最多的宣讲场次。
// 
// | 6:00 | 18 : 00
//  ________________________________会议室_______________________________________
// 
// | 6 : 00       | 8 : 00
//     ___Project1___
// 
//           | 7 : 00       | 9 : 00
//               ___Project2____
// 
//                                    | 10 : 00               | 14 : 00
//                                         _____Project3__________
// 
//                 | 8 : 00                      | 11 : 00
//                            ___Project4_______
// 
//                                                         | 13 : 00        | 15 : 00
//                                                               ___Project5__
// 
//                                                                                  | 16 : 00              | 18 : 00
//  __Project6__
// 
// 应该以Project结束时间来排序，然后依次看每个Project如果能安排，则安排；无法安排，看下一个
int main_bestArrange()
{
	Project projects[] = 
	{
		{6, 8},
		{7, 9},
		{10, 14},
		{8, 11},
		{13, 15},
		{16, 18},
	};

	size_t size = sizeof(projects) / sizeof(Project);
	sort(projects, projects + size, projectCompare);

	size_t projectCount = 0;
	int end = 0;
	for (int i = 0; i < size; i++)
	{
		if (projects[i].start >= end)
		{
			end = projects[i].end;
			++projectCount;
		}
	}

	printf("%d\n", projectCount);
	unordered_set<int> exists;
	projectCount = recur(projects, size, 0, exists);
	printf("%d\n", projectCount);

	return 0;
}